A random process can be defined on the set of states of a finite state machine. A corresponding sequence of random state transitions can be visualised as a path on a trellis diagram. The problem of finding the most probable trellis path which connects two given states is of a great practical importance. This problem arises in such diverse areas as the theory of error-free communication, adaptive planning, the theory of traffic flows. In applications related to communication theories, most probable path-searching algorithms are used to reduce noise from signals transmitted over noisy channels (CDMA2000, Gigabit internet, etc), combat both inter symbol interference and channel noise in magnetic and optical storage devices, maintain communications with deep space research probes (e. g. Galileo).
Markov processes with Gaussian randomness are of particular practical importance. An example is an additive Gaussian white noise (AWGN) communication channel. In this situation, the problem of finding the most probable path reduces to the problem of finding the path of lowest weighting on a trellis, whose branches are equipped with weightings which are real numbers called branch metrics. The latter problem can be solved using methods of maximum likelihood detection. Maximum likelihood detection may include detection of transmitted data and estimation of transmitted symbols which formed part of the data before the effect of noise and/or interference during transmission. Maximum likelihood detection may also include the further step of decoding the data from an encoded format, although this is not an essential feature of a maximum likelihood detector.
In the following discussion, the term “detection” includes the process of recovering signals that are subject to noise and/or known interference, such as inter-symbol interference (ISI) of a known shape. However, if a deliberate encoding process has also been performed on the data, “decoding” is required to recover the signals in their pre-encoded form. For example, if encoding has been performed on purpose to increase resistance of the transmitted signals to noise, then “decoding” can be used to obtain the original pre-encoded signals.
It follows that a “detector” does not require any decoding means for decoding from a deliberate encoding process. However, a detector which includes such decoding means for decoding from a deliberate encoding process may be known as a “decoder”. The decoding means may be configured to work separately or integrally with the detection means. Thus, in the following discussion, a “decoder” is a type of detector which also performs decoding. The hard disk drive examples discussed below are maximum likelihood “detectors”, because the process involved is recovery of signals, where no purposeful encoding was performed on the data. However, everything that is discussed below is also applicable to decoders.
Both detectors and decoders usually output an estimate of a signal before encoding or interference. However, it is possible for a decoder or a detector to output a different sequence, e.g. outputting encoded signals which are corrected for interference and/or noise, or correcting for transmission noise but not correcting for inter-symbol interference.
A prior art method known as the Viterbi algorithm (VA) is particularly well known for solving the above problem of finding the most likely path in a trellis. VA is a recursive procedure, which can be most easily described when used with a known initial state at time t=0, and a known final state at time t=T. VA allows the most likely sequence of states at intermediate times to be found. FIG. 1A shows an example of a two-state trellis diagram which can be used to visualise the VA process. The trellis diagram is a state transition diagram which graphically represents all of the possible states of the system over a sequence of time intervals. The horizontal axis of the trellis represents the times of the state transitions, starting at time t=0 at the left hand side of the trellis, and ending with time t=T at the right hand side of the trellis. The vertical axis represents the possible states of the finite state machine. These possible states are zero and one. Pairs of possible states at adjacent time intervals are connected by lines, with each line representing a state transition. The possible sequences of states over the whole of the time period are represented by the possible paths along the trellis. At time t=0, the system is pre-set to state zero. At the next time interval, t=1, the state may remain as zero or change to one. This is represented by the darker upper and lower lines of the trellis between t=0 and t=1. A change of state from zero to one is represented by the upper line, extending diagonally upwards to connect to one at t=1, and a sequence of all zero states is represented by the lower line, extending horizontally to connect to zero at t=0. At time t=1, if the system is in state one, it may then follow one of two routes, i.e. remain at one, or change to zero. Similarly, if the system is in state zero, it may follow one of a further two routes, i.e. remain at zero, or change to one. At time t=T, the system is reset to zero.
As can be seen from FIG. 1A, the trellis contains one or more paths between each possible initial state and final state. For instance, there are two different paths from the “zero” state at time t=0 to the “zero” state at t=2. These paths are 010 and 000, where the first bit represents the state at time t=0, the second bit represents the state at time t=1, and the third bit represents the state at time t=2. FIG. 1B shows an identical trellis to FIG. 1A, with these two paths in bold lines. VA involves identifying paths between any possible states at time t−1, and each possible state at time t. If more than one path connects from t−1 to a particular state at time t, then VA chooses which of these paths corresponds to the most likely state sequence. Then, the least likely paths are eliminated. The remaining path is called the survivor.
The most likely path can be calculated using numbers known as branch metrics, which indicate the likelihood of each transition. FIGS. 1A and 1B show a number beside each line in the trellis, and this number is the branch metric for that state transition. The branch metrics for all state transitions in a path from time t1 to time t2 can be summed to indicate the likelihood of that particular path occurring. These sums of branch metrics are known as path metrics.
To find a survivor at a given state at time t=t+1, the path metrics of all paths leading to this state are computed by adding appropriate branch metrics to the path metrics of survivors at time t and choosing the path of lowest path metric (also known as the shortest path) leading to the state. This procedure is called add-compare-select operation and it has to be performed for all states at t=t+1. As t=T is reached, there will be only one survivor left, with probability P=1−C1·exp(−C2·T), where C1 and C2 are constants. Thus, the probability approaches 1 as time T increases and C1·exp(−C2·T) becomes small.
A specific example of the application of a use of VA in data transmission will now be described. When data is transmitted over a noisy channel, it is beneficial to encode the data first, using convolution encoding, to allow a degree of error correction. Convolution encoding is a bit level encoding technique where each coded bit is generated by convolving the input bit with the past input bits. Thus the information content of each input bit is spread over a number of coded bits, improving the error resistance of the data. If the encoded bits are then transmitted through a noisy environment, and if a particular encoded bit is very strongly affected by noise, information relating to the original input bits is still preserved in the encoded bits which are less affected by noise. The constraint length K of the convolution encoder is the number of bit shifts over which a single input bit can influence the encoder output. VA can then be used to detect and/or decode the convolution encoded data.
A convolution encoder can be represented by a generator function G(D), defined as follows:
            G      ⁡              (        D        )              =                  ∑                  n          =          0                          K          -          1                    ⁢                          ⁢                        g          n                ⁢                  D          n                      ,where Dn is a delay operator representing a delay of n time units, K is the encoder constraint length and gn's are real numbers, which describe the weight with which past transitions contribute to the current reading.
Another example of convolution encoding occurs in a hard disk read system. Each bit on the disk surface generates a magnetic field, which is detected by the disk read head in order to read the bit, but the read operation is also affected by the magnetic field produced by the neighbouring bits. Thus, any data value obtained in a read operation actually corresponds to a convolution of magnetically recorded bits on the disc. This is known as inter symbol interference (ISI).
VA may be used to decode convolution encoded data, encoded either by deliberate encoding or by an interference process such as inter symbol interference. Various types of a Viterbi detector may be used, depending on the constraint length of the encoder used to encode the data, and the weightings given to previous input data. One type of Viterbi detector is known as “PR4” (partial response system of class IV). “Partial response” refers to the fact that in a partial response system, e.g. in a hard disk drive read system, each bit on the disk gives a multi-bit detected sequence, rather than just a single bit. A PR4 system gives a two bit detected sequence, and the encoder output is constructed from the current encoder input minus a past input delayed by two time units, i.e. an output of 1−D2, where D2 represents a delay of two time units. The following example illustrates a convolution encoder which has an output of 1−D, i.e. the encoder output is constructed from the current encoder input minus a past input delayed by one time unit.
FIG. 2 shows a block diagram of a prior art apparatus for transmission and reception of convolution encoded data. An encoder 100 performs convolution encoding of a stream of input data. The data is then sent over a noisy channel. Noise source 104 represents the effect of noise during transmission of the data. The transmitted data is then received and decoded by a maximum likelihood detector 108. The apparatus of FIG. 2 may represent a communications system, with deliberate convolution encoding of data to increase noise resistance during transmission through a channel. However, it may also represent a hard disk read process, in which the convolution encoding is not deliberate, but is a result of inter symbol interference caused by the magnetic fields of the individual data bits on the disk.
The encoder 100 has a constraint length of two, meaning that a single input bit of the encoder influences two bits of the received data. The encoder 100 has an input 101 for accepting a stream of time dependent input binary data xi, where i represents the time interval. The input data is received by the encoder at a rate of k bits/second. The input 101 of the encoder 100 is connected to an encoder delay element 102. The delay element 102 stores a single bit of data, corresponding to the input bit xi at time i, and outputs this data bit at the following time interval i+1. Thus, at time i, the output of the delay element is xi−1. The output of the delay element 102 is connected to a multiplication unit 103 which multiplies the output value xi−1 by minus one, giving an output of −xi−1. The encoder 100 has a sum unit 104 which is connected to both the encoder input 101 and the output of the multiplication unit 103. The signals xi and −xi−1 are summed by the sum unit 104, to give an output signal of yi=xi−xi−1.
The encoder output signal yi is sent from the output 105 of the encoder 100 via a channel, such as a radio link, a wire, or any other form of data transmission channel, to a detector 108. Noise source 106 represents noise ni generated as the signal yi passes through the channel. The noise source may generate Gaussian white noise, but the actual form of the noise generated does not have to be Gaussian, although in this example, it must be de-correlated noise. A sum unit 107, with inputs connected to the noise source 106 and the encoder output 105, represents the addition of the noise ni to the data yi. Thus, the signal received after the data has passed through the noisy channel is ri=yi+ni. The detector 108 receives the signal ri, and the detector then performs a detecting and decoding process.
FIG. 3 illustrates the trellis diagram structure corresponding to the encoder of FIG. 2, and the method used by a VA detector 108 to detect the received data ri. A series of eight trellis diagrams are shown, representing eight steps of the VA decoding process. A ninth trellis diagram shows a traceback of the optimal path through the trellis. The numbers on the trellis diagrams represent branch metrics, indicating the likelihood that received data corresponds to particular state transitions. Each trellis diagram is similar to that described with reference to FIG. 1, i.e. it has two possible states which are one and zero, and it extends from a known state zero at time t=0 to a known state zero at time t=T. The known states of zero can be set by feeding an initial zero to the encoder to re-set the state of the delay element to zero, and then by transmitting an extra character of zero at the end of the data transmission. A path through the trellis represents a sequence of data which is input to the encoder. Any unique data sequence input to the encoder has a unique path through the trellis.
The state of the trellis, with a value of zero or one, represents a possible value of xi−1. xi−1 is a possible value of the convolution encoder input, which may be stored in the delay element 101. The possible values of the convolution encoder output yi=xi−xi−1 are thus represented by the slope of the lines connecting two states of the trellis at adjacent time intervals i−1 and i. The yi values also represent ideal values of the received data, without any added noise ni. Lines with a zero slope, (such as state zero at t=0 and state zero at t=1) correspond to yi=0. Lines with a left-to-right upwards slope (such as state zero at t=0 and state one at t=1) correspond to yi=1. Lines with a left-to-right downwards slope (such as state one at t=1 and state zero at t=2) correspond to yi=−1. The values of yi are known as “branch labels” of the trellis. The branch labels can be used together with the received data to obtain the branch metrics of the trellis, as will now be described.
When the detector 108 receives the transmitted signal, this received signal ri includes noise ni. Thus, the problem to be solved by the detector is to determine the most likely path through the trellis (i.e. the most likely sequence of characters input to the encoder), based on the noisy received signal. Branch metrics are assigned to the trellis, to indicate the likelihood of each state transition. For Gaussian white noise, the branch metrics can be calculated as (ri−yi)2, i.e. the square of the difference between the received value ri and the expected value yi for that particular state transition. The most likely path is the path with the lowest total weight, i.e. the lowest sum of branch metrics.
When branch metrics are calculated as (ri−yi)2 for the 2-state trellis of FIG. 3, it is common to get a lot of paths having equal path metrics. It may not always be possible, therefore, to choose a single path of greatest likelihood, as one of two equally likely paths must be chosen. Therefore, for the purposes of illustrating the technique of finding a unique path through the trellis using VA, the values shown on FIG. 3 as branch metrics have not been calculated from a chosen set of ri, but instead, short integers have been chosen for each branch metric to ensure different weights for each path. In practice, although the presence of multiple paths of equal likeliness degrades the VA performance, it is often possible to pre-process the data to avoid getting large numbers of equally likely paths.
The first trellis diagram, at the top of FIG. 3, corresponds to step 1 of the detection and/or decoding process. Step 1 concerns the time interval between t=0 and t=1. The state of the system at t=0 is zero, because the delay element was preset to zero before data transmission began. Two possible paths through the trellis during the first time interval are identified as bold lines on the trellis. These correspond to data sequences of 00 and 01 respectively, where the first bit represents the state at time t=0 and the second bit represents the state at time t=1. The 00 path is the lower of the two paths in the trellis, and the 01 path is the higher of the two paths in the trellis. The 00 path has a path metric of 0, but the 01 path has a path metric of 2. As only a single path is formed between the initial state at t=0 and each final state at t=1, no reduction of the trellis is performed at step 1.
The second trellis corresponds to step 2 of the decoding process. The part of the trellis between t=0 and t=2 is now considered. A total of four paths are now possible, namely, 000, 001, 010 and 011, where the first two bits represent the possible paths in step 1, and the third bit represents the state at time t=2. The path metric of each path may be calculated by adding the branch metrics for each state transition on the path. Thus, the path metric of 000 is 0+2=2, of 001 is 0+0=0, of 010 is 2+1=3, and of 011 is 2+1=3. The paths 000 and 010, with path metrics of 2 and 3 respectively, both lead to a final state of 0 at time t=2. Therefore, the 010 can be eliminated, as it has the highest path metric, and the 000 path is the survivor. Similarly, the paths 001 and 011, with path metrics of 0 and 3 respectively, both lead to a final state of 1 at time t=2. Thus, the 011 path can be discarded, and the 001 path is the survivor. The two survivor paths, 001 and 000, are shown in bold on the trellis diagram.
In step 3 of the process, the part of the trellis up to t=3 is considered. The four new possible paths are 0010, 0011, 0000 and 0001, with path metrics of 0, 0, 3 and 4 respectively. The path 0000 with path metric 3, and the path 0001 with path metric 4, can both be eliminated, as these have highest path metrics for final states 0 and 1 respectively. Thus, the survivors are 0010 and 0011, each with a path metric of 0.
In step 4 of the process, the part of the trellis up to t=4 is considered. The four new possible paths are 00100, 00101, 00110 and 00111, with path metrics of 1, 2, 2 and 0 respectively. The paths 00101 and 00110 can be eliminated, as these have highest path metrics for final states 1 and 0 respectively. Thus, the survivors are 00100 and 00111, each with a path metric of 0.
In step 5 of the process, the part of the trellis up to t=5 is considered. The four new possible paths are 001000, 001001, 001110 and 001111, with path metrics of 3, 3, 1 and 0 respectively. The paths 001000 and 001001 can be eliminated, as these have highest path metrics for final states 0 and 1 respectively. Thus, the survivors are 001110 and 001111, with path metrics of 1 and 0 respectively.
In step 6 of the process, the part of the trellis up to t=6 is considered. The four new possible paths are 0011100, 0011101, 0011110 and 0011111, with path metrics of 3, 2, 2 and 1 respectively. The paths 0011100 and 0011101 can be eliminated, as these have highest path metrics for final states 0 and 1 respectively. Thus, the survivors are 0011110 and 0011111, with path metrics of 2 and 1 respectively.
In step 7 of the process, the part of the trellis up to t=7 is considered. The four new possible paths are 00111100, 00111101, 00111110 and 00111111, with path metrics of 2, 4, 3 and 3 respectively. The paths 00111110 and 00111101 can be eliminated, as these have highest path metrics for final states 0 and 1 respectively. Thus, the survivors are 00111100 and 00111111, with path metrics of 2 and 3 respectively.
In step 8 of the process, the part of the trellis up to t=8 is considered. At t=8, the state is set to zero, since a reset signal will be sent at the end of the transmission. Thus, only two paths need be considered instead of four. The two paths are 001111000, 001111110, with path metrics of 2 and 4 respectively. As both paths have the same final state, the path 001111110, which has the highest path metric, can be eliminated. Thus, the only survivor is 001111000, with a path metric of 2.
The ninth trellis shows traceback of the path with the lowest overall path metric, where only the final survivor path is shown in bold, and dead-end paths are no longer shown in bold.
In the absence of any additional noise ni, the received data input to the detector or decoder is an “ideal input”. For a trellis of finite length, an ideal input is a sequence of received data with a corresponding path in the trellis which has a path metric of zero. In other words, for an ideal input, there is a corresponding path which has a sequence of branch labels which is equal to the sequence of received data.
Using VA, the number of steps needed to find the shortest path on a trellis of length N is O(N), which can lead to a prohibitively large computation time. Standard methods of speeding implementations of VA rely on deep pipelining, which leads to large latency delays and increased complexity of implementation due to necessity to manage large amount of memory needed to store information about survivors and their path metrics.
One high speed alternative to the Viterbi algorithm is the Fettweis approach, described in U.S. Pat. No. 5,042,036. Fettweis is a two step process. Firstly, the trellis is divided into multi-step sections, each of length M. Within each of these sections of length M, the least likely paths are eliminated. To do this, Fettweis considers in turn each possible initial state at the start of the length-M section, and considers a subset of the trellis beginning at that state. Depending on the Markov process on which the trellis is based, it is highly likely that after a certain number of state transitions, the highest-likelihood path through the trellis will become independent of the initial state. Fettweis defines a number F, such that after F states, all of the paths are highly likely to converge. E.g. the first F states will depend on the initial state chosen, but after that, all paths will be the same, regardless of which initial state was chosen. F is dependent on the trellis diagram and the initial values of the branch metrics.
Fettweis makes use of this high likelihood of path convergence to reduce part of the trellis to a single path, even though the initial and final states are not previously known. Thus, Fettweis does not need to actually calculate the path through the trellis for every possible initial state of the section. The whole path through the section can be calculated for just one initial state, and then only the first part of the path (which is dependent on the initial state) needs to be calculated for all other initial states. The ability of the Fettweis method to find a likeliest path without knowledge of the initial and final states allows VA to be parallelised, with several sections of length M being reduced in parallel.
When sections of the trellis have been reduced to a single path using the Fettweis method, the sections are re-connected to find the most likely complete path. It is possible to choose overlapping trellis sections to be reduced to connecting sections of single path, so that no further calculation is needed to find the complete path. It is also possible to choose trellis sections to be reduced to obtain a trellis with intermittent sections of single path, and to use standard VA either forwards or backwards from known reduced sections of the path to determine the unknown parts of the path.
However, Fettweis has the considerable disadvantage that the basic sections of input data must each be greater in length than 5K (i.e. 5 times the constraint length). This is because, as a general rule, the non-converging length F which occurs at the start of each section of input data must have a length of 5K or more. The exact value is dependent on the particular structure of the trellis diagram and the values of the branch metrics, however, F will always be at least 5K, due to the need to assign zeros to the start of the sequence, and due to the minimum length required for statistical convergence of the paths from different initial states. In practical maximum likelihood detectors, it is frequently undesirable to use input data sections of such a long length.
A further disadvantage of Fettweis is the large latency between data input to the detector and decoded data output from the detector. This latency is prohibitively high for many practical applications.